package cn.com.guage.dtm.jubian;

import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
import java.util.stream.Collectors;

/**
 * 这段 Java 代码的主要功能是检测进程之间的循环依赖关系。
 * 当输入进程依赖关系后，代码会分析是否存在循环依赖，若有则输出所有循环依赖，若没有则输出 "OK"
 */
public class 进程循环依赖 {

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 1:[2,3],4:[1],3:[4]
        String input = scanner.nextLine();
        //将进程的循环依赖转换为map结构
        Map<Integer, List<Integer>> adjMap = parseInputToMap(input);
        //用于存储检测到的循环依赖
        Set<String> cycles = new HashSet<>();

        //总共四个进程
        //调用 getAllProgress 方法获取所有进程的编号
        Set<Integer> allNodes = getAllProgress(adjMap);

        for (int node : allNodes) {
            LinkedList<Integer> path = new LinkedList<>();
            //对每个进程编号调用深度优先搜索（DFS）方法 dfs 来检测循环依赖
            dfs(node, adjMap, path, cycles);
        }

        //如果没有检测到循环依赖，输出 "OK"；否则，对检测到的循环依赖进行排序并输出。
        if (cycles.isEmpty()) {
            System.out.println("OK");
        } else {
            List<String> sortedCycles = new ArrayList<>(cycles);
            Collections.sort(sortedCycles);
            System.out.println(String.join(" ", sortedCycles));
        }
    }

    private static Map<Integer, List<Integer>> parseInputToMap(String input) {
        Map<Integer, List<Integer>> adjMap = new HashMap<>();
        //该方法使用正则表达式 (\\d+):\\[([^\\]]*)\\] 来匹配输入字符串中的每个进程及其依赖列表
        Pattern pattern = Pattern.compile("(\\d+):\\[([^\\]]*)\\]");
        Matcher matcher = pattern.matcher(input);
        while (matcher.find()) {
            //matcher.group(1) 表示匹配到的进程编号，matcher.group(2) 表示该进程依赖的其他进程编号列表
            int from = Integer.parseInt(matcher.group(1));
            String[] toNodes = matcher.group(2).split(",");
            List<Integer> dependencies = new ArrayList<>();
            for (String s : toNodes) {
                if (!s.isEmpty()) {
                    dependencies.add(Integer.parseInt(s.trim()));
                }
            }
            adjMap.put(from, dependencies);
        }
        return adjMap;
    }

    private static Set<Integer> getAllNodes(Map<Integer, List<Integer>> adjMap) {
        Set<Integer> nodes = new HashSet<>();
        for (Map.Entry<Integer, List<Integer>> entry : adjMap.entrySet()) {
            int from = entry.getKey();
            nodes.add(from);
            for (int to : entry.getValue()) {
                nodes.add(to);
            }
        }
        return nodes;
    }

    private static Set<Integer> getAllProgress(Map<Integer, List<Integer>> adjMap){
        Set<Integer> nodes = new HashSet<Integer>();
        for (Map.Entry<Integer, List<Integer>> entry : adjMap.entrySet()) {
            int from = entry.getKey();
            nodes.add(from);
            for (int to : entry.getValue()) {
                nodes.add(to);
            }
        }
        return nodes;
    }

    private static void dfs(int current, Map<Integer, List<Integer>> adjMap,
                            LinkedList<Integer> path, Set<String> cycles) {
        //如果当前节点已经在路径中，说明发现了一个循环依赖。提取循环中的节点，排序后将其转换为字符串并存储在 cycles 中
        if (path.contains(current)) {
            int index = path.indexOf(current);
            List<Integer> cycle = new ArrayList<>(path.subList(index, path.size()));
            Collections.sort(cycle);
            String s = cycle.stream()
                    .map(String::valueOf)
                    .collect(Collectors.joining());
            cycles.add(s);
            return;
        }

        path.addLast(current);
        for (int neighbor : adjMap.getOrDefault(current, Collections.emptyList())) {
            dfs(neighbor, adjMap, path, cycles);
        }
        path.removeLast();
    }
}